/**
 * \file Tree.h
 * \brief Tree definition and declaration class
 * \author Edouard ROGE
 * \date 8 September 2012
 */
#ifndef _TREE_
#define _TREE_

#include "List.h"
#include "Core/Memory/HeapObject.h"

// Parcours arbre DFS BFS avec iterator

/**
 * \class Tree
 * \brief Tree class with template
 */
template <class T>
class Tree
{
public:

	/**
	 * \class Node
	 * \brief Tree Node
	 */
	class Node : public HeapObject
	{
	public:

		/**
		 * \fn Node();
		 * \brief Default constructor
		 */
		Node();

		/**
		 * \fn Node(const T & _element);
		 * \param _element node object
		 * \brief Constructor with parameter
		 */
		Node(const T & _element);

		/**
		 * \fn ~Node();
		 * \brief Destructor
		 */
		~Node();

		/**
		 * \fn void AddChild(Node * _pChild);
		 * \param _pChild child value to add
		 * \brief add a child to the children list
		 */
		void AddChild(Node * _pChild);

		/**
		 * \fn void RemoveChild(Node * _pChild);
		 * \param _pChild child to remove
		 * \brief remove a child from the children list and all its children too
		 */
		void RemoveChild(Node * _pChild);

		/**
		 * \fn Node * FindChild(const T & _childValue) const;
		 * \param _childValue value of the child to retrieve
		 * \brief retrieve child, icluding the child of child ... etc
		 */
		Node * FindChild(const T & _childValue) const;

		/**
		 * \fn void DeleteChildren();
		 * \brief delete all the children and their children (recursive)
		 */
		void DeleteChildren();

		/**
		 * \fn Node* GetChild(const T & _childValue) const;
		 * \param _childValue value of the child to retrieve
		 * \brief retrieve child
		 */
		Node* GetChild(const T & _childValue) const;

		/**
		 * \fn const List<Node*> & GetChildren() const;
		 * \return list of children
		 * \brief retrieve children list
		 */
		const List<Node*> & GetChildren() const;

		/**
		 * \fn void SetValue(const T & _value);
		 * \param _value new value for the object node
		 * \brief Set node object value
		 */
		void SetValue(const T & _value);

		/**
		 * \fn const T & GetValue() const;
		 * \return value of the node object
		 * \brief Set node object value
		 */
		const T & GetValue() const;

		/**
		 * \fn bool IsLeaf() const;
		 * \return true if the node is a leaf, ie it has no child
		 * \brief check if the node is a leaf
		 */
		bool IsLeaf() const;

		/**
		 * \fn operator T & ();
		 * \brief cast operator
		 */
		operator T & ();

		/**
		 * \fn operator const T & () const;
		 * \brief cast operator
		 */
		operator const T & () const;

		/**
		 * \fn template < class S > friend bool operator == (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2);
		 * \param _node1 node1
		 * \param _node2 node2
		 * \return true if node1 is equal to node2
		 * \brief operator ==
		 */
		template < class S > friend bool operator == (const Node & _node1, const Node & _node2);

		/**
		 * \fn template < class S > friend bool operator != (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2);
		 * \param _node1 node1
		 * \param _node2 node2
		 * \return true if node1 is not equal to node2
		 * \brief operator !=
		 */
		template < class S > friend bool operator != (const Node & _node1, const Node & _node2);

	private:

		/** object of the node */
		T m_object;

		/** parent node */
		Node * m_pParent;

		/** children node */
		List<Node *> m_pChildren;

		friend class Tree<T>;
	};

	/** Tree<T>::Iterator */
	typedef Node *		Iterator;

	/** Tree<T>::ConstIterator */
	typedef const Node*	ConstIterator;

	/**
	 * \fn Tree();
	 * \brief Default constructor
	 */
	Tree();

	/**
	 * \fn Tree(const Tree<T> & _tTree);
	 * \brief Copy constructor
	 */
	Tree(const Tree<T> & _tTree);

	/**
	 * \fn ~Tree();
	 * \brief Destructor
	 */
	~Tree();

	/**
	 * \fn void Clear();
	 * \brief Clear the tree, remove all the elements
	 */
	void Clear();

	/**
	 * \fn void Insert(const T & _element);
	 * \param _element element to insert
	 * \brief insert an element at the end of the list
	 */
	void Insert(const T & _element);

	/**
	 * \fn void Insert(Iterator _it, const T & _element);
	 * \param _it place where the element is inserted
	 * \param _element element to insert
	 * \brief insert an element to the position given by the iterator
	 */
	void Insert(Iterator _it, const T & _element);

	/**
	 * \fn Iterator Remove(Iterator _it);
	 * \param _it place to remove an element
	 * \brief remove an element from the tree and all its children
	 */
	void Remove(Iterator _it);

	/**
	 * \fn Iterator Root();
	 * \return a pointer on the root element
	 * \brief root iterator
	 */
	Iterator Root();

	/**
	 * \fn ConstIterator Root() const;
	 * \return a pointer on the root element
	 * \brief root iterator
	 */
	ConstIterator Root() const;

	/**
	 * \fn Iterator Find(const T & _element);
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in Tree
	 */
	Iterator Find(const T & _element);

	/**
	 * \fn ConstIterator Find(const T & _element) const;
	 * \param _element element to find
	 * \return iterator pointing on this element if find, otherwise returns end iterator
	 * \brief find element in Tree
	 */
	ConstIterator Find(const T & _element) const;

	/**
	 * \fn Tree<T> & operator = (const Tree<T> & _Tree);
	 * \param _Tree Tree to copy
	 * \return (*this) with new values
	 * \brief operator =
	 */
	Tree<T> & operator = (const Tree<T> & _Tree);

	/**
	 * \fn template < class S > friend bool operator == (const Tree<S> & _Tree1, const Tree<S> & _Tree2);
	 * \param _Tree1 Tree1
	 * \param _Tree2 Tree2
	 * \return true if Tree1 is equal to Tree2
	 * \brief operator ==
	 */
	template < class S > friend bool operator == (const Tree<S> & _Tree1, const Tree<S> & _List2);

	/**
	* \fn template < class S >friend  bool operator != (const Tree<S> & _Tree1, const Tree<S> & _Tree2);
	* \param _Tree1 Tree1
	* \param _Tree2 Tree2
	* \return true if Tree1 is not equal to Tree2
	* \brief operator !=
	*/
	template < class S > friend bool operator != (const Tree<S> & _Tree1, const Tree<S> & _Tree2);


private:

	/** root node */
	Node * m_pRoot;
};

template<class T>
Tree<T>::Node::Node()
: m_pParent(NULL)
{
}

template<class T>
Tree<T>::Node::Node(const T & _element)
: m_object(_element), m_pParent(NULL)
{
}

template<class T>
Tree<T>::Node::~Node()
{
}

template<class T>
void Tree<T>::Node::AddChild(Node * _pNode)
{
	m_pChildren.Insert(_pNode);
}

template<class T>
void Tree<T>::Node::RemoveChild(Node * _pChild)
{
	typename List<Tree<T>::Node*>::Iterator it=m_pChildren.Find(_pChild);
	if(it!=m_pChildren.End())
	{
		m_pChildren.Remove(it);
	}
}

template<class T>
void Tree<T>::Node::DeleteChildren()
{
	for(typename List<Tree<T>::Node*>::Iterator it = m_pChildren.Begin(); it !=m_pChildren.End(); it=it->Next())
	{
		Node * pNode = (*it);
		pNode->DeleteChildren();
		delete pNode;
	}
	m_pChildren.Clear();
}

template<class T>
typename Tree<T>::Iterator Tree<T>::Node::FindChild(const T & _childValue) const
{
	if(m_object==_childValue)
		return this;

	for(typename List<Tree<T>::Node*>::ConstIterator it = m_pChildren.Begin(); it!=m_pChildren.End(); it=it->Next())
	{
		Tree<T>::Node* pNode = (*it);
		Node * pRes = pNode->FindChild(_childValue);
		if(pRes)
			return pRes;
	}

	return NULL;
}

template<class T>
typename Tree<T>::Iterator Tree<T>::Node::GetChild(const T & _childValue) const
{
	for(typename List<Tree<T>::Node*>::ConstIterator it = m_pChildren.Begin(); it!=m_pChildren.End(); it=it->Next())
	{
		Tree<T>::Node* pNode = (*it);
		if(pNode->GetValue()==_childValue)
			return pNode;
	}

	return NULL;

}

template<class T>
const List<typename Tree<T>::Node*> & Tree<T>::Node::GetChildren() const
{
	return m_pChildren;
}

template<class T>
void Tree<T>::Node::SetValue(const T & _value)
{
	m_object=_value;
}

template<class T>
const T & Tree<T>::Node::GetValue() const
{
	return m_object;
}

template<class T>
bool Tree<T>::Node::IsLeaf() const
{
	return (m_pChildren.Begin()==m_pChildren.End());
}

template<class T>
Tree<T>::Node::operator T & ()
{
	return m_object;
}

template<class T>
Tree<T>::Node::operator const T & () const
{
	return m_object;
}

/**
 * \fn template < class S > bool operator == (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2);
 * \param _node1 node1
 * \param _node2 node2
 * \return true if node1 is equal to node2
 * \brief operator ==
 */
template < class S >
bool operator == (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2)
{
	if(_node1.m_object != _node2.m_object)
		return false;

	typename List<typename Tree<S>::Node*>::ConstIterator it1=_node1.m_pChildren.Begin();
	typename List<typename Tree<S>::Node*>::ConstIterator it2=_node2.m_pChildren.Begin();

	for( ; it1!=_node1.m_pChildren.End(), it2!=_node2.m_pChildren.End(); it1=it1->Next(), it2=it2->Next() )
	{
		if((*it1)!=(*it2))
			return false;
	}

	return true;
}

/**
 * \fn template < class S > bool operator != (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2);
 * \param _node1 node1
 * \param _node2 node2
 * \return true if node1 is not equal to node2
 * \brief operator !=
 */
template < class S >
bool operator != (const typename Tree<S>::Node & _node1, const typename Tree<S>::Node & _node2)
{
	return !(_node1==_node2);
}


template <class T>
Tree<T>::Tree()
: m_pRoot(NULL)
{
}

template <class T>
Tree<T>::Tree(const Tree<T> & _tTree)
: m_pRoot(NULL)
{
	// TODO
}

template <class T>
Tree<T>::~Tree()
{
	Clear();
}

template <class T>
void Tree<T>::Clear()
{
	Remove(Root());
	m_pRoot = NULL;
}

template <class T>
void Tree<T>::Insert(const T & _element)
{
	Insert(Root(), _element);
}

template <class T>
void Tree<T>::Insert(Iterator _it, const T & _element)
{
	if(!m_pRoot)
		m_pRoot = new Node(_element);
	else
		_it->AddChild(new Node(_element));
}

template <class T>
void Tree<T>::Remove(Iterator _it)
{
	if(_it!=NULL)
	{
		Node * pNode = _it;
		pNode->DeleteChildren();
		if(pNode->m_pParent)
			pNode->m_pParent->RemoveChild(pNode);
		delete pNode;
	}
}

template <class T>
typename Tree<T>::Iterator Tree<T>::Root()
{
	return m_pRoot;
}

template <class T>
typename Tree<T>::ConstIterator Tree<T>::Root() const
{
	return m_pRoot;
}

template <class T>
typename Tree<T>::Iterator Tree<T>::Find(const T & _element)
{

}

template <class T>
typename Tree<T>::ConstIterator Tree<T>::Find(const T & _element) const
{

}

template <class T>
Tree<T> & Tree<T>::operator = (const Tree<T> & _Tree)
{
	return (*this);
}

/**
 * \fn template < class S > bool operator == (const Tree<S> & _Tree1, const Tree<S> & _Tree2);
 * \param _Tree1 Tree1
 * \param _Tree2 Tree2
 * \return true if Tree1 is equal to Tree2
 * \brief operator ==
 */
template < class S >
bool operator == (const Tree<S> & _Tree1, const Tree<S> & _List2)
{
	return (*_Tree1.m_pRoot)==(*_Tree1.m_pRoot);
}

/**
* \fn template < class S > bool operator != (const Tree<S> & _Tree1, const Tree<S> & _Tree2);
* \param _Tree1 Tree1
* \param _Tree2 Tree2
* \return true if Tree1 is not equal to Tree2
* \brief operator !=
*/
template < class S >
bool operator != (const Tree<S> & _Tree1, const Tree<S> & _Tree2)
{
	return !(_Tree1==_Tree2);
}

#endif // _TREE_
